1. Field of Invention
This invention relates to the field of graph visualization, and specifically to the field of constructing abstractions of graphs, using a computer, for the purpose of human understanding. In this context, the word graph is used in the mathematical sense, consisting of a collection of vertices joined by edges.
2. Background of the Invention
Graphs are presented to humans with the intent of conveying information. The presentation is made on a computer screen, driven by a computer, usually in an interactive environment, so that the user can control the presentation. The layout of the graph, and appearance of its elements, are chosen to portray those aspects of the graph that are thought to be of interest at the time. As the graph becomes large, clever layouts fail to be sufficient to create a picture that can be comprehended easily, and the intended information is not communicated readily, if at all.
To a small extent, this may be addressed in an interactive interface by zooming, panning, and distorting a fixed layout. In particular, fisheye views can offer some selected detail in the context of the entire graph. But these approaches, while always useful as augmentations, do not go very far towards appreciating large graphs.
A more fruitful approach is to present the human viewer with an abstraction of the graph. The abstraction is itself a graph a simplification that retains the salient features of the underlying raw graph. To be of much utility, the abstraction method must offer means of reducing the graph""s complexity while still communicating the important aspects. Since the definition of important aspects varies not only with the raw graph, the project, and the human viewer, but also with the moment, the abstraction method must be versatile and rapid.
The needs for graph abstraction have been recognized for a long time, and the prior art teaches much about graph element elision and composition.
To obtain composition (grouping) of vertices, classical graphs have been augmented with an additional graph, here called a composition graph, that specifies how vertices may be grouped. The nature of this composition graph, and its interaction with the raw (classical) graph, has followed an assortment of models.
Eick and Wills (S. G. Eick and G. J. Wills, Navigating Large Networks with Hierarchies, Proceedings of Visualization ""93, IEEE Computer Society Press, Los Alamitos, Calif., 1993, pp. 204-210) grouped vertices by defining a composition graph whose form was a forest and whose leaves were raw graph vertices. Clusters represented by internal nodes in the forest could be opened and closed to obtain abstractions. This so-called clustered graph model was used by Huang and Eades (M. L. Huang and P. Eades, A Fully Animated Interactive System for Clustering and Navigating Huge Graphs, Graph Drawing, 6th International Symposium, GD ""98, Lecture Notes In Computer Science, No. 1547, S. H. Whitesides, ed., Springer, 1998, pp. 374-383) in their disclosure of the DA-TU system in which abstractions of a clustered graph are obtained by opening and closing clusters independently, and clusters may be hidden from the drawing; in their system, clusters are arranged in local regions and outlined by boxes.
Sugiyama and Misue, 1991 (K. Sugiyama and K. Misue, Visualization of Structural Information: Automatic Drawing of Compound Digraphs, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 21, No. 4, July/August 1991, pp. 876-892) suggested using a more general model than clustered graphs. Their compound graphs employ a composition graph that is still a tree, but whose vertices may all be raw graph vertices. In other words, edges representing both adjacency and inclusion are permitted. Each cluster may be open or closed. When a cluster is closed, its contents do not appear; when open, its contents are drawn in a convex region.
It is common practice in graph visualization programs to permit the ad hoc condensation of collections of vertices and permit hiding of vertices. Representative systems are disclosed by Kimelman et al. (D. Kimelman, B. Leban, T. Roth, and D. Zernik, Reduction of Visual Complexity in Dynamic Graphs, Graph Drawing, DIMACS International Workshop, GD ""94, Lecture Notes In Computer Science, No. 894, R. Tamassia and I. G. Tollis, eds, Springer, 1995, pp. 218-225), Frolich and Werner (M. Frolich and M. Werner, Demonstration of the Interactive Graph Visualization System da Vinci, Graph Drawing, DIMACS International Workshop, GD ""94, Lecture Notes In Computer Science, No. 894, R. Tamassia and I. G. Tollis, eds, Springer, 1995, pp. 266-269), Sander (G. Sander, Graph Layout Through the VCG Tool, Graph Drawing, DIMACS International Workshop, GD ""94, Lecture Notes In Computer Science, No. 894, R. Tamassia and I. G. Tollis, eds, Springer, 1995, pp. 194-205), Benz (H. Benz, KGB: A Customizable Graph Browser, Graph Drawing, Symposium on Graph Drawing, GD ""95, Lecture Notes In Computer Science, No. 1027, F. J. Brandenburg, ed., Springer, 1996, pp. 20-23), Sugiyama and Misue, 1996 (K. Sugiyama and K. Misue, A Generic Compound Graph Visualizer/Manipulator: D-ABDUCTOR, Graph Drawing, Symposium on Graph Drawing, GD ""95, Lecture Notes In Computer Science, No. 1027, F. J. Brandenburg, ed., Springer, 1996, pp. 500-503), Huang and Eades (1998), and Carmignani et al. (A. Carmignani, G. DiBattista, W. Didimo, F. Matera, and M. Pizzonia, Visualization of the Autonomous Systems Interconnections with Hermes, Graph Drawing, 8th International Symposium, GD 2000, Lecture Notes In Computer Science, No. 1984, J. Marks, ed., Springer, 2001, pp. 150-163).
Herman et al. (I. Herman, G. Melan xc3xa7 on, and M. S. Marshall, Graph Visualization and Navigation in Information Visualization: A Survey, IEEE Transactions on Visualization and Computer Graphics, Vol. 6, No. 1, January-March 2000, pp. 24-43) offer an overview of the work in graph visualization.
Despite the considerable work reported in this area, the prior art fails to address many graph abstraction needs.
To begin, many of the systems assume special structure to the raw graph, and do not consider the possibility of multiple raw graphs contributing to the abstraction. In practice, raw graphs have arbitrary structure that must be accommodated, including the possibilities that the raw graphs may contain loops and that each pair of adjacent vertices may be joined by perhaps thousands of edges, as might result by representing state transitions, transactional information, or multifaceted relationships between vertices. Rendering all of such edges in a drawing is likely to be distracting; performing analysis on such graphs may also be expensive if all edges need to be traversed repeatedly. In some cases, multiple edges between a pair of vertices should be retained, but abstractions disclosed in the prior art do not teach the handling of such a situation.
As mentioned above, it is desirable to collect groups of vertices and represent each by a composite vertex. Composite vertices can, in turn, also contain other composites. The optimum directed graph that represents this vertex composition, the composition graph, may not necessarily form a tree: raw graph vertices can be present in more than one group, as can composite vertices. Such situations would arise when describing multiple inheritance for class design, or subsystems that appear in multiple places (and perhaps multiple levels) in hardware design. In general, the graph showing the relation between composite vertices and raw graph vertices is an arbitrary directed acyclic graph. Yet no disclosure of a system employing a composition graph other than a forest is offered by the prior art, and such a generalization would not be accommodated in existing systems in an obvious way.
The prior art offers no abstraction methods in which one can surface a portion of a closed composite vertex""s content, or suppress the effects of a portion of a closed composite vertex.
The removal of edges or vertices from abstractions can lead to a deceptive picture if the viewer is not kept aware of such hiding, yet the prior art does not teach methods for doing this.
In consideration of the problems detailed above and the limitations enumerated in the partial solutions thereto, an object of my invention is to provide a method that will construct graph abstractions on a computer for human presentation.
Another object of my inventions is to accommodate an arbitrary directed acyclic graph as a composition graph.
Another object of my invention is to accommodate raw graphs of arbitrary nature, including loops and multiple edges between each pair of vertices.
A further object of my invention is to provide abstraction combining multiple raw graphs.
A still further object of my invention is to permit the exposure of arbitrary contents of closed composite vertices.
Another object of my invention is to permit the hiding of the effects of arbitrary contents of closed composite vertices.
Yet another object of my invention is to construct a graph abstraction rapidly for interactive use.
In order to attain the objectives described above, according to an aspect of my invention, there is provided a method for constructing graph abstractions, the steps of which are summarized below.
My invention may be thought to comprise two stages. In the first stage, constituent raw graphs are combined to produce a base graph. At this time, raw graphs are combined, and the many edges in the raw graphs are represented by (usually fewer) composite edges in the base graph. In the second stage, the base graph is reduced to an abstraction graph, in accordance with vertex composition, dispersion state of composite vertices, visibility of vertices and edges, and other choices by the viewer.
There are at least two purposes for factoring the problem in this manner. The first stage performs operations whose settings will likely not change frequently, the latter stage carries out directives that, in practice, will likely change as the human viewer peruses the raw graphs, moving through a family of abstractions. The work to create the base graph, then, will not be repeated often and keeping this intermediate base graph avoids extra work in each response to an abstraction change. In addition, the base graph is available for analytic functions to operate on, providing a ready way to study a representation of the graph containing all of the vertices.
Even if only a single raw graph is involved, having the base graph exist as a separate object from the raw graph permits multiple views (in separate windows) possibly involving different choices for combining edges and so on.
The first stage reduces one or more raw graphs to a base graph B, in accordance with viewer-supplied choices that specify how each raw graph is to contribute to the base graph, how the operations of combining them are defined, how multiple edges are to be reduced, if at all, and which elements, if any, are to excluded from the base graph. In practice, this stage is often a significant component, but its details are unimportant to my invention.
In the event that only one raw graph is involved and that one does not feel a need to reduce multiple edges, one may choose to effectively skip the first stage by using the single raw graph directly as the base graph.
The second stage of my invention, which builds the abstraction graph G from the base graph B, includes the operations of computing the initial vertex set VINIT, computing the set of showing vertices VSHOW, setting the vertex set of the abstraction graph equal to VSHOW, and inducing edges in the abstraction graph.
The second stage has many inputs set explicitly or implicitly by the human viewer. First, a composition graph V is needed, specifying how vertices from the raw graphs are grouped into composite vertices. The composition graph is a directed graph whose sinks are raw graph vertices and whose edges each lead from a containing composite vertex to a contained composite or raw vertex. It is acyclic and simple, but otherwise arbitrary. C may be trivial, in the sense of having no composite vertices (and no edges) or may be very complex, defining composite vertices within composite vertices to great depth. The composition graph may derive from manual grouping by the human viewer, may be built from an automated function, or may result from a combination of the two. For ease of exposition, let M denote the set of composite vertices.
The membership of a composite vertex may contain a representative member a member that serves as a leader. In hierarchical graphs, for example, this distinguished member occurs naturally: if one chooses to group vertices such that a vertex and its children form a composite, then the parent is the representative of the membership. Having a raw graph representative of a composite""s membership results in presentation and navigation that is more easily understood. If composite vertex a has a representative, it will be denoted r(a). If b=r(a), one may also say that a=rxe2x88x921 (b). Assignments of representatives are considered part of the composition graph.
Note that permitting composite representatives effectively implements the compound graph model of abstraction; if no representatives are defined, the clustered graph model applies.
Composite vertices defined by the composition graph may either be dispersed or marshaled. If dispersed, their contents may show (if not hidden for another reason); if marshaled, the contents will (usually) be represented by the composite vertices in the abstracted graph. The dispersal state of composite vertices is usually controlled directly by the human viewer. Let D, a subset of M, denote the set of dispersed composite vertices.
Edges in the base graph whose adjacent vertices have disappeared into marshaled composites may or may not induce edges in the abstraction. Many useful options controlling such behavior may by provided. Suppose that a marshaled composite vertex c appears in the abstraction graph, and, for the nonce, let S denote the set of descendants of c in the composition graph that do not appear in the abstraction graph. One would likely want base graph edges adjacent to some members of S to appear in the abstraction graph, adjacent to c. In other words, c would act as a proxy for a subset of S for the purpose of inducing abstraction graph edges. Several natural choices for this proxy scope arise. On one extreme, one could let c act as a proxy for all members of S. On the other extreme, one could specify that c would act as a proxy only for its representative member, should one exist. Being more generous, the proxy scope for c could be its immediate children on the composition graph, that is, the base vertices that are contained immediately in the group of vertices represented by the composite vertex. A slightly broader choice consists of the children of c and their representatives. In practice, many of these choices are useful. Clearly, other choices are possible.
It turns out that having two proxy scope settings is useful: one to be applied when considering an edge having one adjacent vertex visible and one buried in composites, and another to be used when both adjacent vertices are within marshaled composites.
In addition to offering choices of proxy scope, it is also useful to provide another option for controlling induced edges. Suppose a base graph edge joins base graph vertices v and w. If neither vertex is present in the abstraction, but proxies for both v and w do appear in the abstraction, should an edge be constructed between the proxies? Not necessarily. Those proxies may actually be the same vertex; the human viewer has the option of allowing loops to be created in such a situation; that option is embodied here in the question of whether internal edges are permitted or not.
Vertex visibility information is provided through human viewer directives and automated functions. While a vertex will either appear or not in any given abstraction graph, each vertex in the composition graph and base graph has one of three visibility settings: VISIBLE, HIDDEN, or AUTOMATIC. A vertex marked as VISIBLE will appear in the abstraction, regardless of dispersal state or visibility of any containing composite vertices. Conversely, the mark of HIDDEN will prevent a vertex from appearing. A vertex marked as AUTOMATIC will appear if there is a path from a source in the composition graph, or from another vertex that appears, to the vertex in question, that does not have a hidden or marshaled vertex. If a vertex is the representative of a composite vertex, then the visibility setting is always applied to the composite vertex and the representative acts as if it were labeled as AUTOMATIC.
All vertices in the composition graph C have a visibility setting. Let SV denote the set of vertices that are marked VISIBLE, and let SH denote the set of vertices that are marked HIDDEN. All vertices not in the union of SV and SH are considered to be marked AUTOMATIC.
In addition, base graph edges may be marked as hidden by the human viewer, and will not induce edges in the abstraction graph.
Given the composition graph and the visibility settings, one can identify a set of starting vertices VINIT=(SV+sources (C))xe2x88x92SH. These vertices will appear in the abstraction, regardless of dispersal state of composite vertices.
To build the abstracted graph, many intermediate structures may be built. To facilitate the exposition, let A denote the allowable composition graph consisting of the composition graph C less the hidden vertices in SH.
Given A, the set of showing vertices, VSHOW, may be obtained by a forward traversal on A from the set VINIT, by recording each vertex visited, and not traversing to children of marshaled composite vertices.
For each vertex v in the base graph, one can define the incomplete one-sided proxy function, p1 (v), to be the set of vertices in the abstraction graph that act as proxies for v in the event that v does not appear in the abstraction graph, to be used when considering an edge in which exactly one of its adjacent vertices is within marshaled composites. Similarly, one can define the incomplete two-sided proxy function, p2 (v), to be the set of vertices in the abstraction graph that act as proxies for v in the event that v does not appear in the abstraction graph, and to be used when considering an edge in which both adjacent vertices are within marshaled composites. In addition, one can define the complete one-sided and two-sided proxy functions, denoted p1* and p2*, respectively. They are similar to p1 and p2, respectively, but are based on the entire composite graph C, rather than A . The complete proxy functions identify showing vertices that would have been proxies, had no vertices that are descendants of showing vertices been hidden. All four of these functions are computed in accordance with the choices of proxy scope set by the viewer.
As suggested hereinabove, many choices for proxy functions, driven by proxy scope choices by the viewer, are beneficial. There are several natural choices for assigning proxies; the appropriate choice, selected by the viewer, depends upon the problem and what is desired at the time. In each case, a proxy for a vertex b in B not appearing in G is a composite vertex that is in G and is an ancestor of b in C. Moreover, the proxy""s ancestry from b cannot be through another vertex in G, since the latter would serve as a better proxy instead. To facilitate the discussion, one may use the following notation: given any graph Hand vertex v, let c(v|H)={W|(v, w) in E(H)} denote the children of vertex v in graph H. In particular, the children c (a|C) in C of composite vertex a in M constitute the membership of a.
Some natural choices for proxy functions, corresponding to suggested proxy scopes hereinabove, are listed here. In general, let p(b) denote one of the incomplete proxy functions for base vertex band let p*(b) denote the corresponding complete proxy function. It may happen that the set p(b) contains many members, one member, or none, with similar behavior for p*(b).
For the proxy scope of representative only, one has       p    ⁢          xe2x80x83        ⁢          (      b      )        =      {                                                      {                                                r                                      -                    1                                                  ⁢                                  xe2x80x83                                ⁢                                  (                  b                  )                                            }                        ,                                                                              if                ⁢                                  xe2x80x83                                ⁢                                  r                                      -                    1                                                  ⁢                                  xe2x80x83                                ⁢                                  (                  b                  )                                ⁢                                  xe2x80x83                                ⁢                exists                ⁢                                  xe2x80x83                                ⁢                and                ⁢                                  xe2x80x83                                ⁢                                  r                                      -                    1                                                  ⁢                                  xe2x80x83                                ⁢                                  (                  b                  )                                            ∈                              V                ⁢                                  xe2x80x83                                ⁢                                  (                  G                  )                                                      ;                                                            φ            ,                                                otherwise            ,                              
with             p      *        ⁢          xe2x80x83        ⁢          (      b      )        =      {                                                      {                                                r                                      -                    1                                                  ⁢                                  xe2x80x83                                ⁢                                  (                  b                  )                                            }                        ,                                                                              if                ⁢                                  xe2x80x83                                ⁢                                  r                                      -                    1                                                  ⁢                                  xe2x80x83                                ⁢                                  (                  b                  )                                ⁢                                  xe2x80x83                                ⁢                exists                ⁢                                  xe2x80x83                                ⁢                and                ⁢                                  xe2x80x83                                ⁢                                  r                                      -                    1                                                  ⁢                                  xe2x80x83                                ⁢                                  (                  b                  )                                            ∈                              V                ⁢                                  xe2x80x83                                ⁢                                  (                  G                  )                                                      ;                                                            φ            ,                                                otherwise            .                              
For the proxy scope of immediate children, one has
p(b)={vxcex5V(G)|bxcex5c(v|A)}
with
p*(b)={vxcex5V(G)|bxcex5c(v|C)}
For the proxy scope of immediate children and their representatives, one has       p    ⁢          xe2x80x83        ⁢          (      b      )        =      {                                                                                                                                  {                                              v                        ∈                                                  V                          ⁢                                                      xe2x80x83                                                    ⁢                                                      (                            G                            )                                                                                                                "RightBracketingBar"                                    ⁢                  b                                ∈                                  c                  ⁢                                      xe2x80x83                                    ⁢                                      (                                                                  v                        ⁢                                                                              "LeftBracketingBar"                            A                                                    )                                                ⁢                                                  xe2x80x83                                                ⁢                        or                        ⁢                                                  xe2x80x83                                                ⁢                                                  r                                                      -                            1                                                                          ⁢                                                  xe2x80x83                                                ⁢                                                  (                          b                          )                                                                    ∈                                              c                        ⁢                                                  xe2x80x83                                                ⁢                                                                              (                            v                                                    "RightBracketingBar"                                                ⁢                        A                                                              )                                                              }                        ,                                                              if              ⁢                              xe2x80x83                            ⁢                              r                                  -                  1                                            ⁢                              xe2x80x83                            ⁢                              (                b                )                            ⁢                              xe2x80x83                            ⁢              exists                        ;                                                                                                                                                      {                                              v                        ∈                                                  V                          ⁢                                                      xe2x80x83                                                    ⁢                                                      (                            G                            )                                                                                                                "RightBracketingBar"                                    ⁢                  b                                ∈                                  c                  ⁢                                      xe2x80x83                                    ⁢                                                            (                      v                                        "RightBracketingBar"                                    ⁢                  A                                            )                        ⁢                          xe2x80x83                                                            otherwise            ,                              
with             p      *        ⁢          xe2x80x83        ⁢          (      b      )        =      {                                                                                                                                                          {                                                  v                          ∈                                                      V                            ⁢                                                          xe2x80x83                                                        ⁢                                                          (                              G                              )                                                                                                                          "RightBracketingBar"                                        ⁢                    b                                    ∈                                      c                    ⁢                                          xe2x80x83                                        ⁢                                          (                                                                        v                          ⁢                                                      "LeftBracketingBar"                            C                            )                                                    ⁢                                                      xe2x80x83                                                    ⁢                          or                          ⁢                                                      xe2x80x83                                                    ⁢                                                      r                                                          -                              1                                                                                ⁢                                                      xe2x80x83                                                    ⁢                                                      (                            b                            )                                                                          ∈                                                  c                          ⁢                                                      xe2x80x83                                                    ⁢                                                      (                            v                                                                                              "RightBracketingBar"                                        ⁢                    C                                                  )                            }                        ,                                                              if              ⁢                              xe2x80x83                            ⁢                              r                                  -                  1                                            ⁢                              xe2x80x83                            ⁢                              (                b                )                            ⁢                              xe2x80x83                            ⁢              exists                        ;                                                                                                                                                                                                        {                                                      v                            ∈                                                          V                              ⁢                                                              xe2x80x83                                                            ⁢                                                              (                                G                                )                                                                                                                                    "RightBracketingBar"                                            ⁢                      b                                        ∈                                          c                      ⁢                                              xe2x80x83                                            ⁢                                              (                        v                                                                              "RightBracketingBar"                                ⁢                C                            )                        ⁢                          xe2x80x83                                                            otherwise            ,                              
And for the proxy scope of all descendants, one has
p(b)={vxcex5V(G)|∃ directed path (v,v1,v2, . . . , vn,b) in A vi∉V(G)∀i}
with
p*(b)={vxcex5V(G)|∃ directed path (v,v1, v2, . . . , vn,b) in C vi∉V(G)∀i}
According to an aspect of my invention, the last major step in constructing an abstraction graph is to examine each edge in the base graph, one at a time, and determine what edges, if any, should be induced in the abstraction graph to reflect said base graph edge. Each determination is based on what vertices appear in the abstraction graph and on the proxy functions. The edges are induced as needed as the process proceeds.
It is highly desirable to provide cues to the viewer of an abstraction graph that indicate where elision has taken place, thereby indicating where further investigation will be fruitful and avoiding misrepresentation. According to an aspect of my invention, this strongly-felt desire may be met by marking vertices in the abstraction graph as having torn edges. The process of determining such markings is best conducted by examining each base graph edge in turn as part of the process of inducing edges in the abstraction graph. Consider, for example, a base graph edge (a, b) in B such that a is in G, but where no proxy for b is present in the abstraction. Then (a, b) will induce no edges in C, and a will lack an otherwise-expected adjacent edge. To alert the viewer that a neighbor for a exists and that a potential outgoing edge could be added by suitable changes in visibility, the vertex a may be marked as having outgoing torn edges. Alternatively, if a is not in G but has proxies in G, then those proxies may be marked as having outgoing torn edges. Similarly, if instead b is in G and a has no proxies, then b would be marked as having incoming torn edges. More generally, when an edge fails to appear because an endpoint does not have a proxy in the appropriate incomplete proxy function, torn edge markings should result at each vertex that would have had an induced edge if the vertex did have a proxy. To determine what vertices would have been proxies, the complete proxy functions are used.
In more detail, now, consider the handling of a single base graph edge e=(v1, v2), in which the two issues of inducing edges in the abstraction graph and of marking vertices with torn edges in the abstraction graph are to be addressed. Two steps may be taken. First, all appropriate edges will be induced in the abstraction graph. Second, if no edges were induced in the abstraction graph, proxy vertices will be marked as having torn edges, as appropriate. The second step is not taken if edges were induced in the first step.
For this discussion, define, for any base vertex v,       g    ⁢          xe2x80x83        ⁢          (      v      )        =      {                                                                      r                                  -                  1                                            ⁢                              xe2x80x83                            ⁢                              (                v                )                                      ,                                                            if                  ⁢                                      xe2x80x83                                    ⁢                                      r                                          -                      1                                                        ⁢                                      xe2x80x83                                    ⁢                                      (                    v                    )                                    ⁢                                      xe2x80x83                                    ⁢                  exists                  ⁢                                      xe2x80x83                                    ⁢                  and                  ⁢                                      xe2x80x83                                    ⁢                                      r                                          -                      1                                                        ⁢                                      xe2x80x83                                    ⁢                                      (                    v                    )                                                  ∈                                  V                  ⁢                                      xe2x80x83                                    ⁢                                      (                    G                    )                                                              ;                                                                        v            ,                          otherwise              .                                          
The first step may be broken down by case. In the case that the edge should be hidden, as directed by the viewer, the first step is complete without inducing any edges. In the case that both g(v1) and g(v2) are in G, an edge from g(v1) to g (v2) is added to G. In the case that g(v1) is present in G but g(v2) is not, edges may be induced in G going from g(v1) to proxies of v2. Similarly, if g(v2) is present in G but g(v1) is not, edges may be induced in G going from proxies of v1 to g(v2). In the case that neither g(v1) nor g(v2) is present in G, then edges may be induced in G going from proxies of v1 to proxies of v2. The details of which proxies are involved depend upon the desires of the viewer and the embodiment of my invention.
The second step, that of marking vertices as having torn edges, may also be divided by case. In the case that both g(v1) and g(v2) are in G, the vertex g(v1) is marked as having outgoing torn edges and the vertex g(v2) is marked as having incoming torn edges. In the case that g(v1) is present in G but g(v2) is not, g(v1) may be marked as having outgoing torn edges and proxies of v2 may be marked as having incoming torn edges. Similarly, in the case that g(v2) is present in G but g(v1) is not, proxies of v1 may be marked as having outgoing edges and g(v2) may be marked as having incoming torn edges. In the case where neither (v1) nor g(v2) is present in G, then proxies of v1 may be marked as having outgoing torn edges and proxies of v2 may be marked as having incoming torn edges. The details of this step depend upon the desires of the viewer and the embodiment of my invention.
According to these observations and an aspect of my invention, there is provided a method for building an abstraction graph from a set of raw graphs in accordance with a composition graph, a visible vertices set, a hidden vertices set, a dispersed composite vertices set, and a hidden edge set, comprising the steps of building a base graph from said set of raw graphs; computing a set of starting vertices consisting of a union of the visible vertices set and the set of source vertices of the composition graph, less the hidden vertices set; determining a set of showing vertices by recording each vertex visited in a directed traversal on the composition graph from said set of starting vertices, said directed traversal excluding the members of the hidden vertices set, and said directed traversal excluding edges leaving vertices that are not members of the dispersed composite vertices set; placing the members of said set of showing vertices in the abstraction graph as its vertices; computing a set of proxy functions, each member of which maps each vertex in said base graph that is not in said set of showing vertices to a subset of the members of said set of showing vertices; and inducing edges in the abstraction graph from edges in the base graph using said set of proxy functions to map adjacent vertices of edges in the base graph to vertices in the abstraction graph.